package reviewAlgorithms.dynamicProgramming;

public class ClimbStairs {
    public static void main(String[] args) {
        System.out.println(climbStairs(5));
    }
    public static int climbStairs(int n) {
        if (n < 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        int index = 2;
        while (index <= n){
            dp[index] = dp[index - 1] + dp[index - 2];
            index ++;
        }
        return dp[n];

    }

    public static int climbStairs1(int n) {
        if (n <= 2) {
            return n;
        }
        int pre2 = 1, pre1 = 2;
        for (int i = 2; i < n; i++) {
            int cur = pre1 + pre2;
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }

}
